// https://www.lintcode.com/problem/fibonacci/

class Solution {
public:
    /**
     * @param n: an integer
     * @return: an ineger f(n)
     */
     
    // 不超出Integer的斐波那契数很少，仅有50个左右。不考虑溢出。

    int fib[1000];
    int dfs(int n)
    {
        if (fib[n] != -1)
            return fib[n];
        return dfs(n - 1) + dfs(n - 2);
    }
    int fibonacci(int n) {
        // 使用纯的递归，复杂度是O(2^n),TLE
        // if (n <= 2) return n - 1;
        // return fibonacci(n - 2) + fibonacci(n - 1);
    
        // 记忆化的递归,TLE
        // memset(fib, -1, sizeof(fib));
        // fib[0] = 0;
        // fib[1] = 1;
        // return dfs(n - 1);
        
        // 递推.AC
        vector<int> nums(n, 0);
        nums[0] = 0;
        nums[1] = 1;
        for (int i = 2; i < n; ++i)
        {
            nums[i] = nums[i - 1] + nums[i - 2];
        }
        return nums[n - 1];
    
        int a = 0;
        int b = 1;
        for (int i = 0; i < n - 1; ++i)
        {
            int tmp = a + b;
            a = b;
            b = tmp;
        }
        return a;
    }
};